package com.study.algorithm.ordinaryArray;

import java.util.Arrays;

public class ProductExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;//数组长度
        int[] answer = new int[n];//结果数组
        //1.计算左侧乘积
        answer[0] = 1;//没有左侧元素，所以为1
        for (int i = 1; i < n; i++) {
            //当前左侧积 nums[0] × nums[1] × ... × nums[i-2] 就是 answer[i-1]
            answer[i] = answer[i - 1] * nums[i - 1];//即当前前缀乘积=前一个前缀成绩*前一个元素
        }
        //2.计算右侧乘积，并合并到answer中
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * rightProduct;//合并左侧和右侧的乘积
            rightProduct *= nums[i];//更新rightProduct,即当前右侧乘积=当前右侧乘积*当前元素（供下一个 i-1 使用）
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        ProductExceptSelf productExceptSelf = new ProductExceptSelf();
        System.out.println(Arrays.toString(productExceptSelf.productExceptSelf(nums)));
    }
}
